package zijie;

public class FindKthNumber_440_12 {

    // n = 15 , k = 2
    public int findKthNumber(int n, int k) {
        int cur = 1;
        k = k - 1;//扣除掉第一个cur = 1的节点，表示这个数已经数过了，如果k==1,这是其实就返回cur了
        while(k>0){
            int num = getNode(n,cur,cur+1);// 以cur开头的，有num个数，比如以1开头的有7个数,以11开头的只有1个数
            if(num<=k){//第k个数不在以cur为根节点的树上
                cur+=1;//cur在字典序数组中从左往右移动
                k-=num;
            }else{//在子树中
                cur*=10;//cur在字典序数组中从上往下移动
                k-=1;//刨除根节点
            }
        }
        return cur;
    }
    public int getNode(int n, long first, long last){
        int num = 0;
        while(first <= n){
            num += Math.min(n+1,last) - first;//比如n是195的情况195到100有96个数
            first *= 10;
            last *= 10;
        }
        return num;
    }

    public int findKthNumber2(int n, int k) {
        int cur = 1;
        k = k - 1;
        while (k > 0){
            int num = getNode2(n,cur,cur + 1);
            if(num <= k){
                cur += 1;
                k -= num;
            }else{
                cur *= 10;
                k -= 1;
            }
        }
        return cur;
    }

    public int getNode2(int n,long first,long last){
        int num = 0;

        while (first <= n){
            num += Math.min(n + 1,last) - first;
            first *= 10;
            last *= 10;
        }
        return num;

    }


    public static void main(String[] args) {
        FindKthNumber_440_12 findKthNumber_440_12 = new FindKthNumber_440_12();
        int kthNumber = findKthNumber_440_12.findKthNumber(15, 3);
        System.out.println(1);
    }
}
